package 栈.字符串解码;

import java.util.LinkedList;
/**
 * 题目描述：
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 * 测试用例保证输出的长度不会超过 105。
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 * 力扣：https://leetcode-cn.com/problems/decode-string/
 * 力扣第 394 题
 * */
/**
 * 题目思路：
 * 建立两个栈，一个栈用于保存数字，一个栈用于保存字符串。
 * 遇到左括号，将数字和字符分别存入数字栈和字符栈中 。
 * 遇到右括号，将数字栈中的数字取出，然后循环添加k次字符串到结果中
 * 在拼接返回
 * */
class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0; // 用于存储数字
        // 存储数字的栈
        LinkedList<Integer> stack_multi = new LinkedList<>();
        // 储存字符串的栈
        LinkedList<String> stack_res = new LinkedList<>();
        // 遍历字符串
        for(Character c : s.toCharArray()){
            // 遇到'['的处理
            if(c == '['){
                // 将数字保存到数字栈里面
                stack_multi.addLast(multi);
                // 将当前字符串保存到字符串栈里面
                stack_res.addLast(res.toString());
                // 重置数字为0
                multi = 0;
                // 重置字符串为空
                res = new StringBuilder();
            }else if(c == ']'){
                StringBuilder tmp = new StringBuilder();
                // 去除最近的一次次数
                int cur_multi = stack_multi.removeLast();
                // 循环添加进去
                for(int i = 0;i < cur_multi;i++){
                    tmp.append(res);
                }
                // 与前面的字符合并
                res = new StringBuilder(stack_res.removeLast() + tmp);
            }
            // 遇到数字的处理，当前数字乘10左移
            else if(c >= '0' && c <= '9'){
                multi = multi * 10 + Integer.parseInt(c + "");
            }
            // 遇到普通字符的处理
            else{
                res.append(c);
            }
        }
        return res.toString();
    }
}